﻿using System;
using System.Diagnostics;
using System.Linq;

namespace ProjectEuler
{
    internal class Problem18
    {
        private int[][] triangle = new int[15][];
        private int[][] maxSums = new int[15][];

        public void Solve()
        {
            var rowCount = 15;
            init();

            maxSums[0] = new[] {triangle[0][0]};
            for (int i = 1; i < rowCount; i++)
            {
                var sumPrevRow = maxSums[i - 1];
                var sumrow = new int[i+1];
                var trirow = triangle[i];

                sumrow[0] = sumPrevRow[0] + trirow[0];
                
                for (var j = 1; j < i + 1; j++)
                {
                    if (j == i)
                    {
                        sumrow[j] = sumPrevRow[j - 1] + trirow[j];
                        continue;
                    }

                    sumrow[j] = Math.Max(sumPrevRow[j - 1], sumPrevRow[j]) + trirow[j];
                }

                maxSums[i] = sumrow;
            }

            var maxSum = maxSums[rowCount - 1].Max();

            Debug.WriteLine("problem 18: " + maxSum);
        }

        private void init()
        {
            triangle[0] = new int[] {75};
            triangle[1] = new int[] {95, 64};
            triangle[2] = new int[] {17, 47, 82};
            triangle[3] = new int[] {18, 35, 87, 10};
            triangle[4] = new int[] {20, 04, 82, 47, 65};
            triangle[5] = new int[] {19, 01, 23, 75, 03, 34};
            triangle[6] = new int[] {88, 02, 77, 73, 07, 63, 67};
            triangle[7] = new int[] {99, 65, 04, 28, 06, 16, 70, 92};
            triangle[8] = new int[] {41, 41, 26, 56, 83, 40, 80, 70, 33};
            triangle[9] = new int[] {41, 48, 72, 33, 47, 32, 37, 16, 94, 29};
            triangle[10] = new int[] {53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14};
            triangle[11] = new int[] {70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57};
            triangle[12] = new int[] {91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48};
            triangle[13] = new int[] {63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31};
            triangle[14] = new int[] {04, 62, 98, 27, 23, 09, 70, 98, 73, 93, 38, 53, 60, 04, 23};
        }
    }
}